class Solution:
    def maxCoins(self, nums) -> int:
        if len(nums) == 0:
            return 0
        nums.insert(0,1)
        nums.append(1)
        return self.getMaxNum(nums, 0, len(nums)-1, {})

    def getMaxNum(self, nums, start, end, cache={}):
        if (start, end) in cache:
            return cache[(start, end)]
        if start >= end - 1:
            cache[(start, end)] = 0
            return 0
        if start == end - 2:
            cache[(start, end)] = nums[start] * nums[end] * nums[start + 1]
            return cache[(start, end)]
        thisMax = 0
        for i in range(start + 1, end):
            left = self.getMaxNum(nums, start, i, cache)
            right = self.getMaxNum(nums, i, end, cache)
            thisMax = max(thisMax, left + right + nums[start] * nums[i] * nums[end])
        cache[(start, end)] = thisMax
        return thisMax


if __name__ == '__main__':
    so = Solution()
    n = [2,3,7,9,1]
    r = so.maxCoins(n)
    print(r)
